""" sbak/tree.py - General-purpose tree structures.

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    NOTE: There is a chance that this module will become more generalized
    and will be known as `graph` rather than `tree`. As I see it, a "tree" is
    just a specific kind of graph, or a specific subset of graph functionality.
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    NOTE: The later portion of this module's documentation was written in a
    hurry and, as such, may not be worded very clearly. It should be cleaned up
    as soon as possible.
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    The purpose of this module is to provide a basis for implementing
    data structured in tree-like hierarchies using objects that have
    the following qualities:
    
    - Each banch node may have any number of sub nodes.
    - Any node may be added to any branch node and later removed using
      simple interfaces.
    - Each branch node must keep subnodes in order. (Think lists, not sets.)
    - Each node must be able to indicate its parent node.
    - Each node may have multiple parent branches, but each parent must be
      indicated by a unique name.
    - Each subnode (child) cannot appear in a branch node (parent)
      more than once. (Think sets, not lists.)
    
    The classes defined here are intended for use as bases or mixins.
    The only data they store is that which is needed to keep track of
    relations between each other.
    
    ~~~ Nodes ~~~
    
    This module defines several "interface classes." (See the section entitled
    "Conventions Used in This Library" of the `sbak` package documentation.)
    
    There are two interfaces defined here: `INode` and `IBranch`. These two
    interfaces are the basis for tree- and/or graph-like structuring of data in
    ScrollBack.
    
    INode is for objects that are meant to be a part of a tree (or perhaps a
    graph) of such objects. Nodes that do not have the capacity to have
    children are called "leaves."
    
    A node can have the capacity to be a child of one or more "branches" (see
    below). The exact number of parents that a node can have depends on the
    node. The INode interface does not indicate exactly how a node should be
    related to its parents, if any, although there is a certain way that is
    expected as a matter of convention. ScrollBack provides a means of adhering
    to this system easily; see the next section for details.
    
    The only thing INode requires is that it implements a method called
    `get_root` that returns the "main tree" root node, if there is one.
    
    - Branches -
    
    IBranch is for branch nodes. A "branch node" is one that can have an
    arbitrary number of subnodes (children) that are all of the same type.
    Branches are like lists in that they have the `append`, `remove`, `insert`,
    `extend` and `index` methods and can also be subscripted. They are like
    sets because they also support the `add`, `discard`, and `update`, methods,
    and only ever contain one occurence of each of the items they contain.
    (Attempting to use the `append` method to append a node that is already in
    the branch will raise an exception.)
    
    Informally, a node that does not fully implement the IBranch interface
    may be referred to as a "branch" when its `get_root` method is called by
    the `get_root` method of another node while trying to locate the main tree
    root node. It is useful to refer to nodes that contain multiple links (see
    `sbak.base.LinkableM`) as "branches" even though they are not in any way
    related to the IBranch interface, though such branches may not have all the
    required methods to make them "true" branches.
    
    - Multiple Parentage -
    
    A node can be the child of multiple parents, but each parent must be a
    unique type of branch; a node cannot be a child to two different branches
    of the same type. Conversely, each "formal" branch can have any number of
    children, but they must all be of the same type. (An "informal" branch can
    only have a certain number of children, and each one must be of a unique
    type--that's not the kind of branch we're talking about here.)
    
    When a node `A` is added as a child to a branch `C` of a particular type
    when `A` is already a child to another branch `B` that is of the same
    type as `C`, then `A` will be removed from `B` before being added to `C`.
    
    If `A` is added to a branch `D` that is of a different type than either
    `B` or `C`, then `A` will remain a child of `B` (or `C`, whichever it was
    a part of), but will still be added to `D` nonetheless.
    
    A node uses a separate attribute to refer to each of its parents. Each of
    these attributes can only refer to a parent of a particular type. An
    exception is raised if an attempt is made to assign a parent to a node's
    attribute that expected a different type of parent. NOTE: A parent's "type"
    in this situation is determined by the presence of a particular method of
    the parent, NOT by the class of the parent object. Similarly, when a child
    is added to a parent, the child's "type" is determined by the presence of
    a certain method and not by the class of the child.
    
    ~~~ Classes ~~~
    
    There are several classes defined in this module. They make use of
    metaclassing and "magic" class attributes for the purpose of dynamic
    method generation.
    
    - The `AbstractNode` Class -
    
    On its own, the `AbstractNode` class does not provide _any_ functionality
    whatsoever--not even an __init__ method. It's usefulness comes from the
    "magic" behavior of its metaclass, `NodeM`.
    
    Through the metalcass `NodeM`, `AbstractNode` provides access to a special
    class attribute called "__branch_names". If present, this attribute needs
    to be a dictionary, or anything that can be converted to a dictionary with
    the `dict` function.
    
    Each key in `__branch_names` indicates the "type string" of a parent that
    the node class can have. This must correspond to the value of the
    `__branching_name` attribute of a proper branch class. The value
    corresponding to each key is the type string of the current class in
    relationship to the type string of the parent, and must correspond to the
    `__subnode_name` attribute of a proper branch class.
    
    `NodeM` makes use of the name-mangling feature of the Python interpreter to
    prevent `__branch_name` from being interpreted repeatedly.
    
    TODO: Give more details.
    
    The `AbstractBranch` class implements some of the IBranch interface, but
    not all of it. Like `AbstractNode`, however, it has custom metaclass that
    can be used to add the missing functionality automatically. The metaclass
    is called `BranchM`, and it is a subclass of `NodeM`, which means that the
    special behavior of either or both classes may be used.
    
    The special attributes `__branching_name` and `__subnode_name` can be used
    to trigger the automatic method generation features of `BranchM`. If either
    of these is present, both of them must be, or else a RuntimeError exception
    will be raised.
    
    `__branching_name` indicates the "type string" that must be used by nodes
    that want to make instances of the branch class their parent.
    `__subnode_name` indicates a type string that a node must have in order for
    an instance of a branch class to be able to make a node its child.
    
    To reiterate:
    
    `__branch_names`
        A class attribute of a node class (this includes branches) which, when
        present, will generate the properties necessary for allowing instances
        of the class to be children of branch classes that support particular
        type strings. The value of the attribute is a dict or dict-compatible
        object where the keys are the type strings of compatible branch
        classes, and the values are the type strings for the class instances
        with respect to the type string of each parent branch.
        
    `__branching_name`
    `__sudnode_name`
        Together, these class attributes generate the necessary methods to a
        branch class to allow it to support children with a particular type
        string. `__branching_name` indicates the type string of the parent
        class as seen by children, and `__subnode_name` indicates the type
        string of the child from the parent's perspective.
        
        
    FIXME: Explain what a "type string" is, or else reword the docs so that this poorly-defined term isn't needed.
    
    ~~~ Automatic Method Displacement ~~~
    
    There is a possibility that the user of the method-generating features of
    the classes defined above may want to add extra behavior to one or more of
    the generated methods. One way to do this is through subclassing; the user
    auto-generates the methods by creating an "intermediate" class from one of
    the node classes, then creates another class from that class which
    overrides the methods generated in the intermediate class.
    
    The automatic method generation features of the node classes provide an
    alternate means of adding functionality to the auto-generated methods.
    Whenever a class defines the special attributes but also defines a method
    with the same name as one of the methods that would be generated, the
    auto-generated method has a "_" (underscore) prepended to its name. No
    other change is made to the method; however, it is assumed that the
    manually-defined method will invoke the automatically-defined method at
    some point in its code, normally at the beginning.

    ~~~ Examples ~~~
    
    #1) This creates a branch class called `Spam` and a child node class called
    `Foo`. Instances of `Spam` will be able to have subnodes of `Foo`, and
    instances of `Foo` will be able to have instances of`Spam` as their parent
    branch. The example shows the creation of two `Spam` instances and two
    `Foo` instances, and shows how the foos can be added to a spam and then
    moved to another spam.
    
        from sbak.tree import *
    
        class Spam(AbstractBranch):
            __branching_name = "spam"
            __subnode_name = "foo"
        
        class Foo(AbstractNode):
            __branch_names = {"spam" : "foo"}
        
        s1 = Spam()
        s2 = Spam()
        f1 = Foo()
        f2 = Foo()
        
        s1.add(f1)
        f1.spam         # Gives s1
        
        f2.spam = s1
        s1[0]           # Gives f1
        s1[1]           # Gives f2
            
        f1.spam = s2
        s1[0]           # Gives f2 only
        s2[0]           # Gives f1
        
        s2.add(f2)
        s2.add(f2)      # The second time it does nothing
        s2.append(f2)   # Raises ValueError
        s1[0]           # Raises IndexError; all children are in s2 now
        
        f1.spam = None
        s2.remove(f2)
        len(s2)         # Gives 0; all children have been removed from s2.
    
    #2) This shows how auto-generated methods can be "displaced" by the manual
    creation of methods with the same names. Calling a "displaced" method is
    kind of like calling a method of the superclass, except that there is no
    actual superclass.
    
        class Spam(AbstractBranch):
            __branching_name = "spam"
            __subnode_name = "foo"
            
            def append(self, child):
                
                # Auto-generated `append` method renamed to `_append` since
                # another `append` already existed in the class body.               
                
                self._append(child)
                print "Appended", child, "to", self
            
        class Foo(AbstractFoo):
            __branch_names = {"spam" : "foo"}
            
            def set_spam_internal(self, spam, unlinked=False):
                
                # Auto-generated `set_spam_internal` method displaced to
                # `_set_spam_internal`, which is called below.
                
                self._set_spam_internal(spam, unlinked)
                print self, "parent spam set to", spam
        
        myspam = Spam()
        myfoo = Foo()
        myfoo.spam = myspam
        # "<Foo object at 0x...> parent spam set to <Spam with 1 children>"
        
        otherfoo = Foo()
        myspam.append(otherfoo)
        # "<Foo object at 0x...> parent spam set to <Spam with 2 children>"
        # "Appended <Foo object at 0x...> to <Spam with 2 children>"
"""

import operator

import sbak.base

class INode(object):
    """ Interface for nodes of trees.
    
        This interface is for any object that will be part of a tree or graph
        structure of some kind. The only requirement of a node is that it has
        a primary "root" of some kind 
        
        This interface is normally implemented indirectly through
        the implementation of one of its primary sub-interfaces (subclasses
        that are also interfaces). These are IBranch and ILeaf.
    """
    
    def get_root():
        """ Returns the main tree root node of the current node.
        
            This method should call the `get_root()` method of the next object
            that is on the path from this node to the "main tree root" node
            and return that value.
            
            It is up to the current node to decide what object is the next node
            on the path to the root.
            
            Below is an example tree structure: 
            
            A
            +--B
            |  |
            |  +--C
            |  +--D
            |
            +--E
            |-- ...and so on...
            
            Each letter is an object that represents a node in the tree. Each
            object implements the `get_root()` method. Calling any of them
            should return the object `A`, since it is at the root of the tree.
            `get_root()` does this by calling `get_root()` of another object,
            which then calls `get_root()` of another object still, and so on
            until `A.get_root()` is called, which simply returns self; that is,
            `A`. This is illustrated in the calling chains below:
            
            From `A`:
            
                A.get_root() -> A
                
            From `B`:
            
                B.get_root() -> A.get_root() -> A
            
            From `C`:
            
                C.get_root() -> B.get_root() -> A.get_root() -> A
                
            From `D`:
            
                D.get_root() -> B.get_root() -> A.get_root() -> A
            
            From `E`:
            
                E.get_root() -> A.get_root() -> A
                
            The key thing to note here is that the object ultimately returned
            by each `get_root()` is `A`, since it is considered the "main tree
            root" of each object in the tree.
            
            Alternately, a node can return `None` to indicate that the root is
            unknown, which usually means the node node is not part of the "main
            tree." This would be the case if the node were part of a hybrid
            tree/graph structure and there was no obvious path to the root from
            the node's location, or if there is not root at all.
        """

class NodeM(sbak.base.ObjectM):
    """
        TODO: DOCUMENT ME!
    
        ~~~ Primary Parent ~~~
    
        The special class attribute `__primary_parent` is used to indicate
        which parent of the node is the "primary" one. If this attribute is
        present in a class definition at the same time as the `__branch_names`
        attribute, `NodeM` will generate a method called `get_root` which is
        used to return the root of the node's main tree. The method is defined
        as follows:
        
            def get_root(self):
                return self.PARENT.get_root()
                
        PARENT in the method definition is replaced by the value of
        `__primary_parent`. The value must be one of the keys in
        `__branch_names`; if it is not, a ValueError will be raised with an
        explanation of the problem.
    """
    
    def __init__(cls, name, bases, dict):
        """ TODO: Document me! """
        super(NodeM,cls).__init__(name, bases, dict)
        
        dict_ = dict
        from __builtin__ import dict
        
        # An AttrView object must be used rather than cls.__dict__ because
        # cls.__dict__ is only a dictproxy and does not support assignment.
        attrs = sbak.base.AttrView(cls)
        
        try:
            # Try to find __branch_names.
            brnames = dict_['_'+name+'__branch_names']
        except KeyError:
            # If __branch_names isn't here, don't do anything.
            pass
        else:
            
            # Make sure that __branch_names is a dict.
            try:
                brnames = dict(brnames)
            except TypeError:
                raise TypeError("__branch_names must be a dict-compatible object, "
                                "not %r" % brnames)
            
            # Find the name of the primary parent, if any.
            try:
                primary_parent = dict_['_'+name+'__primary_parent']
            except KeyError:
                primary_parent = None
            else:
                # Make sure that primary_parent is one of the keys in
                # branch_names.
                if primary_parent not in brnames:
                    raise ValueError(
                        '`__primary_parent` value "%s" is not one of the keys '
                        'in `__branch_names` for node class `%s`'
                        % (primary_parent, name)
                    )
            
            # If __branch_names is here, parse its items into relationships.
            for parent_name, self_name in brnames.iteritems():
                # Name of self's internal instance attribute for the reference
                # to the parent branch
                _parent_name = '_'+parent_name
                
                # Getter used to get self's parent without using _fget_
                # (Works like getattr(self, _parent_name), but faster.)
                self_get_parent = operator.attrgetter(parent_name)
                
                # Getter that returns a setter that sets self's internal
                # reference to the parent
                get_self_set_parent_internal = operator.attrgetter(
                                                'set_'+parent_name+'_internal')
                
                # Getter that returns the method used to internally append a
                # child to a parent.
                get_parent_append_child_internal = operator.attrgetter(
                                                'append_'+self_name+'_internal')
                
                # Geter that returns the method used to internally remove a
                # child from the parent.
                get_parent_remove_child_internal = operator.attrgetter(
                                            'remove_'+self_name+'_internal')
                
                # Getter that returns self's parent
                _fget_parent = operator.attrgetter(_parent_name)
                
                # Setter that sets self's internal reference to the parent
                def set_parent_internal(self, val, unlinked=False):
                    """ TODO: Document me! """
                    parent = self_get_parent(self)
                    if parent is not val and parent is not None and not unlinked:
                        get_parent_remove_child_internal(parent)(self)
                    setattr(self, _parent_name, val)
                set_parent_internal.__doc__ %= {'self': self_name,
                                               'parent': parent_name}
                set_parent_internal.__name__ =\
                    'set_'+parent_name+'_internal'
                
                # If the class definition included a method with the same name
                # as the one just created, rename the newly created method to
                # something slightly different so that the class definition's
                # method can still be used.
                if set_parent_internal.__name__ in dict_:
                    set_parent_internal.__name__ += '_'
                
                # Setter that sets self's reference to the parent and also
                # adds self to the parent's child list
                def _fset_parent(self,val):
                    if val is not None:
                        try:
                            parent_append_child_internal =\
                                get_parent_append_child_internal(val)
                        except AttributeError:
                            raise TypeError("%r is not a valid %s for %r." %
                                (val, parent_name, self))
                        else:
                            parent_append_child_internal(self)
                    get_self_set_parent_internal(self)(val)
                _fset_parent.__name__ = '_fset_'+parent_name
                
                # Documentation for the parent property
                _doc_parent =\
                """ The %(parent)s for this %(self)s.
                
                    Objects of this class can have a child-parent relationship
                    with compatible objects, where self is the child. In such
                    relationships, the child (self) is called the "%(self)s,"
                    and the parent is called the "%(parent)s."
                    
                    When the `%(parent)s` property of the %(self)s (self) is
                    changed, the %(self)s is added to the %(parent)s's
                    `%(self)s` list automatically and removed from that of the
                    previous `%(parent)s`.
                
                """ % {"self" : self_name, "parent" : parent_name}
                
                # Property that combines self's getter and setter
                p = property(_fget_parent, _fset_parent, None, _doc_parent)
                
                # If a primary parent was specified and it is this parent,
                # then generate a `get_root` based on it.
                if primary_parent == parent_name:
                    def get_root(self):
                        """ Returns the root node for this %(self)s.
                            
                            %(self)s.get_root() -> %(self)s.%(parent)s.get_root()
                            
                            This method relies on %(self)s.%(parent)s having a `get_root`
                            method, so if the %(parent)s does not have one then an
                            AttributeError will most likely occur.
                        """
                        return self_get_parent(self).get_root()
                    get_root.__doc__ %= {"self" : self_name,
                                            "parent" : parent_name}
                    
                    # If the class definition already contains a `get_root`,
                    # rename the one that we just created to something slightly
                    # different so that the existing one is used instead, but
                    # the generated one is still available if it is needed for
                    # any reason.
                    if get_root.__name__ in dict_:
                        get_root.__name__ = "_" + get_root.__name__
                    
                    # Add the `get_root` method.
                    attrs[get_root.__name__] = get_root.__get__(None, cls)
                
                # Add the class attributes to the class
                attrs[_parent_name] = None       # prevents AttributeError
                attrs[parent_name] = p
                attrs[set_parent_internal.__name__] =\
                                        set_parent_internal.__get__(None,cls)
                
        print cls, "NodeM"

class AbstractNode(sbak.base.Object):
    """ TODO: Document me! """
    
    __metaclass__ = NodeM

class IBranch(INode):
    """ Interface for branch nodes of trees.
    
        A branch is a node in a tree or other graph that can have a
        parent-child relationship with any number of child objects. The name
        for the parent in this relationship is known as the 
    """
    
    def append(child):
        """ TODO: Document me! """
    
    def add(child):
        """ TODO: Document me! """
        
    def insert(index, child):
        """ TODO: Document me! """
        
    def remove(child):
        """ TODO: Document me! """
        
    def discard(child):
        """ TODO: Document me! """
    
    def extend(children):
        """ TODO: Document me! """
    
    def update(children):
        """ TODO: Document me! """
        
    def index(child):
        """ TODO: Document me! """
    
    def replace(old, new):
        """ TODO: Document me! """ 

    def __getitem__(index):
        """ TODO: Document me! """
        
    def __setitem__(index):
        """ TODO: Document me! """
    
    def __delitem__(index):
        """ TODO: Document me! """
        
    def __len__():
        """ TODO: Document me! """
        
    def __contains__(child):
        """ TODO: Document me! """
        
    def __iter__():
        """ TODO: Document me! """

class ISearchable(object):
    """ An interface for searchable branches and sudnodes within them.
    
        A "searchable" is a node that can be "searched" in order
        to locate a node with a particular ID. The ID is the value of a
        node's attribute called `id`, not the result of calling the builtin
        `id` function on a node.
        
        The node with the id being searched for can be the node that is being
        searched at present, a subnode of that node (if it is a branch, whether
        formal or informal), a subnode of any of that node's subnodes, and so
        on.
    
        In order to be able to find a node that is deeply nested within a
        branch, each child branch of the branch being searched must also
        properly implement the ISearchable branch down to the level that the
        node being searched for resides.
        
        For example:
        
        A
        |
        +-- B
            |
            +-- C
            |   |
            |   +-- D
            |   |
            |   +-- E
            |
            +-- F
            
        * In order to be able to find node `F` within the tree above when
          starting the search at node `A`, then at least nodes `A` and `B` need
          to implement the ISearchable interface. (`F` itself does not have to
          implement the interface since it does not have subnodes.)
        * In order to be able to find `E` within the tree above when starting
          the search at node `A`, then at least nodes `A`, `B`, and `C` need to
          implement the interface. (`E` itself does not need to implement the
          interface.)
        * When searching for `D` starting at `B`, then only `B` and `C` need to
          implement the interface since `A` is not being used for searching.
    """
    
    def search(id, searched=None):
        """ Search for a node with the given id.
        
            This should first check the `id` of the current node, returning
            the node itself if the `id` attribute of the node is equal to the
            given id. Type checking is not necessary.
            
            If the given id is not equal to the current node's, then the
            `search` method of each subnode should be called for subnodes that
            have a `search` method. The value of the first `search` method to
            return a value other than None should be returned.
            
            If a subnode does not have a `search` method (meaning
            AttributeError is raised when `subnode.search` is accessed), then
            the `id` of the subnode should be checked. If it is equal to the
            value passed, then the subnode should be returned.
            
            The `searched` parameter is used to prevent infinite recursion. If
            None is passed, a new, empty `set` object should be created, and
            this set should be passed as the `searched` parameter to the
            `searched` method of each subnode that has a `find` method. The
            `search` method of each subnode should check to see if it (the
            current subnode) is already in the set; if so, None should be
            returned before `search` is called on further subnodes, unless the
            current subnode's `id` matches the passed `id`. If the current
            subnode is not in the set, it should be added to the set before
            calling `search` on further subnodes.
            
            Any subnode that has neither a `search` method nor a `id` attribute
            should be ignored; an AttributeError for `id` or `search` should
            not cause the search to fail just because a needed attribute was
            missing.
            
            Finally, a ValueError should be raised if `None` is passed as the
            id being searched for, since `None` is not a valid ID. (An object
            that has an `id` of None is said not to have an ID at all.)
            
            See `sbak.tree.AbstractBranch.search` for an implementation of the
            `search` method that works exactly as intended by the explanation
            above.
        """

class BranchM(NodeM):
    """ Metaclass for Branch.
        
        This metaclass is used to autogenerate the methods required for the
        full implementation of the IBranch interface.
        
        See Branch, IBranch, and the `tree` module documentation for more
        information.
    """
    
    def __init__(cls, name, bases, dict):
        super(BranchM, cls).__init__(name, bases, dict)
        
        dict_ = dict
        from __builtin__ import dict
        
        # Default the branching name and subnode name to None. Class modification
        # only occurs later on if BOTH of these change to values other than
        # None.
        bname = None
        sname = None
        
        # Try to find the branching and sudnode names within the class body.
        # If one is not found, set it to None to indicate that it was not
        # found.
        
        try:
            pname = dict_['_'+name+'__branching_name']
        except KeyError:
            pname = None
        
        try:
            sname = dict_['_'+name+'__subnode_name']
        except KeyError:
            sname = None
            
        # Both the branching name (bname) and the subnode name (sname) must
        # be present in the class body in order for class modification to
        # occur. If neither is found, nothing happens and the initialization of
        # the class will end. If only one is found, an exception is raised to
        # indicate that some required information (ie. the missing bname or
        # sname) is missing.
        
        # At least one of the special names were found.
        if any((sname,pname)):
            
            # Both of the special names were found; generate the special
            # methods.
            if all((sname,pname)):
                
                # Getter that returns the method to append a child internally
                self_get_append_child_internal =\
                    operator.attrgetter("append_"+sname+"_internal")
            
                # Getter that returns the method to set a child's parent
                # internally
                child_get_set_parent_internal =\
                    operator.attrgetter("set_"+pname+"_internal")
                
                def append(self, child):
                    """ Append the given child node to the branch.
                    
                        The child given must implement the internal parent
                        setter method with the correct name for this branch.
                        If it does not, a TypeError will be raised.
                        
                        The child must not already be a child of the branch.
                        If it is, a ValueError will be raised.
                    """
                    self_get_append_child_internal(self)(child)
                    child_get_set_parent_internal(child)(self)
                    
                def insert(self, index, child):
                    """ Insert the given child node at an arbitrary point.
                    
                        index:  An index value, starting at 0. Negatives are
                                allowed and are taken relative to the end of
                                the branch's child list.
                                
                        child:  The child to insert. The same rules apply to
                                this argument as to that of the `append`
                                method.
                    """
                    self_get_append_child_internal(self)(child, index)
                    child_get_set_parent_internal(child)(self)
                    
                def remove(self, child):
                    """ Remove the given child from the current branch.
                    
                        The given child must be in the branch. If it is not,
                        a ValueError will be raised.
                        
                        The given child must implement the internal parent
                        setter method with the correct name for the current
                        branch. If it does not, a TypeError will be raised.
                        (This is somewhat redudant since all existing children
                        of a branch should implement the correct internal
                        parent setter method, but nonetheless it may help to
                        catch obscure bugs.)
                    """
                    if child not in self._children:
                        raise ValueError("%r is not a child of this branch."
                                         % child)
                    try:
                        child_set_parent_internal =\
                            child_get_set_parent_internal(child)
                    except AttributeError:
                        raise TypeError("%r is not a compatible node for this "
                                        "branch." % child)
                    child_set_parent_internal(None, True)
                    self_get_remove_child_internal(self)(child)
                
                def extend(self, children):
                    """ Appends each child node in the given sequence to the branch.
                    
                        The given argument must be an iterable sequence, and each
                        item in the sequence must be a unique node. The sequence cannot
                        contain any node that is already a child of the current branch.
                        
                        TypeError will be raised if the given argument is not iterable,
                        or if any item in the sequence is not a compatible node (meaning
                        that it does not have the required internal parent-setting
                        method.)
                        
                        ValueError will be raised if the given sequence contains multiple
                        occurences of the same node, or if the sequence contains any
                        nodes that are already in the current branch.
                        
                        If an error occurs for any of the reasons stated above, then none
                        of the nodes will be added to the branch.
                    """
                    for c in children:
                        if children.count(c) > 1:
                            raise ValueError("%r occurs multiple times in the "
                                "given sequence." % c)
                        if c in self:
                            raise ValueError("%r in the given sequence "
                                "already contained by the current branch." % c)
                        try:
                            child_get_set_parent_internal(c)
                        except AttributeError:
                            raise TypeError("%r in given sequence is not "
                                "a compatible node for the current branch. "
                                % c)
                    for c in children:
                        self.append(c)
                
                def update(self, children):
                    """ Adds each node in the given sequence to the branch.
                    
                        The given argument must be an iterable sequence. Each item in the
                        sequence must be a node compatible with the current branch. All
                        nodes must be compatible nodes for the type of the current
                        branch. If any item in the sequence is not a compatible node, a
                        TypeError will be raised and none of the nodes will be added.
                        
                        The given sequence may contain multiple occurences of the same
                        node, or nodes that are already contained by the branch. Each one
                        is added sequentially to the branch and if a node is found that is
                        already a part of the branch then it is simply ignored and not
                        added.
                        
                        TypeError may be raised if the argument given is not iterable.
                    """
                    for c in children:
                        try:
                            child_get_set_parent_internal(c)
                        except AttributeError:
                            raise TypeError("%r in given sequence is not "
                                "a compatible node for the current branch. "
                                % c)
                    for c in children:
                        self.add(c)
                
                def append_child_internal(self, child, index=None):
                    """ Internally appends or inserts the given child.
                    
                        child:  A node. The same rules apply as for the
                                `append` method.
                        
                        index:  Optional position at which to insert the node.
                                If not given the node is appended to the end of
                                the branch.
                        
                        This method is used to internally append a node to the
                        branch, meaning that the node's parent property for the
                        type of the current branch is not updated.
                        
                        The method is called by `append`, `add`, `insert`,
                        `extend`, and `update`, as well as whenever the current
                        branch is assigned to the parent property of a node
                        that is compatible with the curernt branch. There is no
                        need to call this method directly, unless you are
                        extending its functionality with an override.
                    """
                    if child in self._children:
                        raise ValueError("cannot append %r; already contained."
                                         % child)
                    if index is None:
                        self._children.append(child)
                    else:
                        self._children.insert(index, child)
                append_child_internal.__name__ = "append_"+sname+"_internal"
                
                def remove_child_internal(self, child):
                    """ Removes the given child internally.
                    
                        This will remove the given child node from the current
                        branch without updating the value of the parent
                        property of the node.
                        
                        The given value must be in the branch or else a
                        ValueError will be raised.
                        
                        No checking is done to see if the child is even
                        compatible with the current branch.
                        
                        This method is called by the `remove` and `discard`
                        methods. There is no need to call this method directly
                        unless you are extending its functionality with an
                        override.
                    """
                    self._children.remove(child)
                remove_child_internal.__name__ = "remove_"+sname+"_internal"
                
                # We need an AttrView for what we're about to do because the
                # __dict__ attribute of class objects is immutable (ie. it does
                # not allow item assignment) because its type is some obscure
                # builtin called "dictproxy"
                attrs = sbak.base.AttrView(cls)
                
                # The final steps...
                
                # Create a list of all the methods we've just created.
                funcs = [append, insert, remove, extend, update,
                         append_child_internal, remove_child_internal]
                
                # Iterate over all the methods.
                for func in funcs:
                    # Prepend a "_" to the name of any autogenerated method
                    # whose name appears in the class definition body. This
                    # allows the autogenerated methods to be accessed even when
                    # the user code defines methods of the same names, and
                    # allows, for example, user code to extend the
                    # autogenerated methods with additional functionality.
                    if func.__name__ in dict_:
                        func.__name__ = "_" + func.__name__
                        
                    # Add each method to the class.
                    attrs[func.__name__] = func.__get__(None, cls)
            
            # Error; only one of the special names was found.
            else:
                raise RuntimeError("One of the following is missing: "
                                   "__branching_name, __subnode_name")
                
        print cls, "BranchM"

class AbstractBranch(AbstractNode):
    """ A basic implementation of the common parts of the IBranch interface.
    
        This class partially implements the part of the IBranch interface that
        will be common to all branch classes. For the parts that are not common
        to all branch classes, a combination of automatic implementation using
        the BranchM "magic attributes" and manual implementation should be
        used.
        
        This class also completely implements the ISearchable interface.
    """
    __metaclass__ = BranchM
    
    # Used by the __init__ method for the purpose of cooperative multiple
    # inheritence.
    __init = False
    
    def __init__(self, children=None):
        """ Initializes internal attributes.
        
            This method is only effective once, meaning it is safe to call
            multiple times. (This behavior exists to allow for the
            AbstractBranch instances to be initialized in a multiple
            inheritence scenario when the use of the `super` function is
            not practical.)
        """
        if not self.__init:
            self.__init = True
            self._children = []
            if children is not None:
                self.extend(children)
    
    def __repr__(self):
        return "<%s with %i children>" % (
            self.__class__.__name__, len(self)
        )
    
    def __getitem__(self, i):
        children = self._children
        try:
            return children[i]
        except TypeError:
            for child in children:
                try:
                    if child.localid == i or child.id == i:
                        return child
                except AttributeError:
                    pass
            raise KeyError("no child with index, localid, or id %r" % i)
        
    def __setitem__(self, i, v):
        if isinstance(i, slice):
            raise TypeError("slice assignment not supported.")
        self.replace(i, v)
        
    def __delitem__(self, i):
        if isinstance(i, slice):
            raise TypeError("slice deletion not supported.")
        child = self[i]
        self.remove(child)
        
    def __iter__(self):
        return iter(self._children)
    
    def __contains__(self, child):
        return child in self._children
    
    def __len__(self):
        return len(self._children)
    
    def add(self, child):
        """ Adds the given child node to the current branch.
        
            This will update the parent property of the given node for the
            current branch. If the node was previously a child of another
            branch of the same type as this one, it will be removed from it.
            
            If the given node is already in the branch, nothing happens.
            
            If the given node is not the right type of node for this branch,
            a ValueError will be raised.
        """
        try:
            self.append(child)
        except ValueError:
            pass
    
    def discard(self, child):
        """ Discards the given child node.
        
            The given node's parent property will be set to None.
            
            Nothing will happen if the given node is not a child of this
            branch.
        """
        try:
            self.remove(child)
        except ValueError:
            pass
    
    def replace(self, old, new):
        """ Replace a child with a new one.
        
            old:    Existing child, index of, or leaf ID of. If it is a
                    number, it is interpreted as an index. If it is a
                    string, it will be interpreted as a leaf ID string.
                    If it is an object that is a child of the node, it
                    is unprocessed. Other types of value have undefined
                    behavior, though they MIGHT still work if there is
                    a child that uses the value as its ID.
            
            new:  The child to replace the old child.
            
            The old child must exist in the node, or else a KeyError
            may occur.
            
            The new child must not already be in the tree, or else a
            ValueError may occur.
        """
        try:
            old = self[old]
        except KeyError:
            if old not in self:
                raise KeyError("%r not contained." %  old)
        if new in self:
            raise ValueError("cannot replace %r; replacement %r"
                             "already contained." %
                             (old, new))
        index = self.index(old)
        self.remove(old)
        self.insert(index, new)
    
    def index(self, child):
        """ Returns the index position of the child.
        
            Raises ValueError if the child is not a child of this branch.
        """
        return self._children.index(child)
    
    def search(self, id, searched=None):
        """ Search the branch for a node with the given ID.
        
            branch.search(id) -> node
        
            id:         The ID to search for. This can be any value other than
                        None.
            
            searched:   This is used internally for the purpose of detecting an
                        endless search. Do not pass it.
        
            This method can be used to return a node that exists anywhere
            within the branch, whether it is the branch itself, a subnode of
            the branch, a subnode of a subnode, and so on.
            
            The method searches for a node with an attribute called `id` that
            has a value of the ID passed to the method. The first node with a
            matching `id` attribute is returned. If all nodes are searched and
            the ID was not among them then None is returned.
            
            NOTE: Searching may not entirely accurate in graphs with a cyclic
            relationships between several nodes. (FIXME: Explain this.)
            
            This method requires that branch subnodes of the current branch
            implement the `ISearchable` interface in order for their subnodes
            to be included in the search.
        """
        # Never search for None; that is considered an error.
        if id is None:
            raise ValueError("None is not a valid ID.")
        
        # If the current branch has the ID being searched for, return self as
        # the result of the search.
        try:
            _id = self.id
        except AttributeError:
            pass
        else:
            if _id == id:
                return self
        
        # If this is the initial call to search, initialize the search record.
        # End the search if this branch has already been searched.
        if searched is None:
            searched = set()
        
        # If this is the first time this branch has been searched within the
        # current search record, add the branch to the record.
        if self not in searched:
            searched.add(self)
        else:
            # If this branch is already in the search record, then we are
            # searching a graph with cyclic links and the search cycle has
            # started over. The node with the given ID is either in a part of
            # the graph that is inaccessible from here or else not in the graph
            # at all.
            return None
        
        # Search for the id within each subnode.
        for c in self:
            # See if the current subnode is searchable.
            try:
                search = c.search
            except AttributeError:
                # If it is not searchable, see if its ID is the one being
                # searched for, unless it has no ID.
                try:
                    _id = c.id
                except AttributeError:
                    pass
                else:
                    if _id == id:
                        return c
            # The subnode is searchable.
            else:
                # Search the subnode. If this turns something up, return it,
                # or else continue the search.
                ret = search(id, searched)
                if ret is not None:
                    return ret
        
        # If we made it this far then the ID cannot be found.
        return None